package com.yang.Dp;

/**
 * @Author: yang
 * @Description:
 * @Date: Created in 16:41 2022/8/9
 * @Modified By:
 */

/*
 * 分析一波
 * 1.确定 dp[i] 表示 到第i层需要消耗的最小体力
 * 2.确定递推公式 比如dp[i] 可以由 dp[i - 1] 跨一步 或者 dp[i - 2] 跨两步 到dp[i]
 *                        所以有dp[i] = dp[i - 1] + dp[i - 2]
 *   这里需要注意的是， 最后一层理解为不需要消耗体力 所以返回前一层或前两层的结果中最小的结果
 * 3.数组如何初始化？  dp[1] = cost[0]  dp[2] = cost[1]
 * 4.确定遍历顺序 后一个结果依靠前一个结果  所以从前往后遍历
 * 5.举例推导公式
 * */
public class climbStairs2 {
    public static void main(String[] args) {
        climbStairs2Solution climbStairs2 = new climbStairs2Solution();
        int[] cost = {1,100,1,1,1,100,1,1,100,1};
        System.out.println(climbStairs2.minCostClimbingStairs(cost));
    }
}
class climbStairs2Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length];
        dp[0] = cost[0];
        dp[1] = cost[1];

        for(int i = 2; i < cost.length; i++){
            dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        // 最后一步理解为不需要消耗体力 所以返回前一层或前两层的结果
        return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
    }
}
